//
// Description: 847. 访问所有节点的最短路径
// Created by Loading on 2021/8/6.
//

#include <bits/stdc++.h>

using namespace std;

int shortestPathLength(vector<vector<int>> &graph) {
    /* 使用状态压缩，将路径压缩为 n 位二进制数，为 1 则代表此节点已走过 */
    // 三元组队列：节点，路径掩码，距离
    queue<tuple<int, int, int>> q;
    // 记录当前节点的路径
    unordered_map<int, unordered_set<int>> visit;

    int n = graph.size();
    // 初始化
    for (int i = 0; i < n; ++i) {
        q.emplace(i, 1 << i, 0);
        visit[i].insert(1 << i);
    }

    int res = 0;
    /* BFS */
    while (!q.empty()) {
        auto[x, mask, dist] = q.front();
        q.pop();
        // 判断是否遍历了全部节点
        if (mask == (1 << n) - 1) {
            res = dist;
            return res;
        }
        // 遍历邻接点
        for (auto &v : graph[x]) {
            // 将此节点加入路径
            int mask_v = mask | (1 << v);
            // 防止走重复路线
            if (!visit[v].count(mask_v)) {
                visit[v].insert(mask_v);
                q.emplace(v, mask_v, dist + 1);
            }
        }
    }

    return res;
}

int main() {
    vector<vector<int>> graph = {{1},
                                 {0, 2, 4},
                                 {1, 3, 4},
                                 {2},
                                 {1, 2}};

    cout << shortestPathLength(graph) << endl;
}